package com.leetcode.algorithm.y22.m07;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1200. 最小绝对差
 * 
 * https://leetcode.cn/problems/minimum-absolute-difference/
 * 
 * @author jie.deng
 *
 */
class Question1200Solution01 {
	
	public List<List<Integer>> minimumAbsDifference(int[] arr) {
		// 排序 + 一次遍历
		Arrays.sort(arr);
		List<List<Integer>> list = new ArrayList<>();
		int minDiff = arr[1] - arr[0];
		List<Integer> pair = new ArrayList<>();
		pair.add(arr[0]);
		pair.add(arr[1]);
		list.add(pair);
		for (int i = 2; i < arr.length; i++) {
			if (arr[i] - arr[i - 1] == minDiff) {
				pair = new ArrayList<>();
				pair.add(arr[i - 1]);
				pair.add(arr[i]);
				list.add(pair);
			} else if (arr[i] - arr[i - 1] < minDiff) {
				minDiff = arr[i] - arr[i - 1];
				list.clear();
				pair = new ArrayList<>();
				pair.add(arr[i - 1]);
				pair.add(arr[i]);
				list.add(pair);
			}
		}

		return list;
	}
    
}